115. 不同的子序列

Similar Question

Solution Tips

方案一: 回溯 + 记忆化搜索

和之前子序列的问题类似, 但是参数调换了位置, 是为了更好的理解题意

抓住 “选”，s 要照着 t 来挑选，逐字符考察选或不选，分别来到什么状态？

举例，s 为 babgbag，t 为 bag，末尾字符相同，于是 s 有两种选择：

1. 用 s[s.length-1] 去匹配掉 t[t.length-1]，问题规模缩小：继续考察 babgba 和 ba
2. 不这么做，但 t[t.length-1] 仍需被匹配，于是在 babgba 中继续挑，考察 babgba 和 bag

是否用它去匹配，是两种不同的挑选方式，各自做下去所产生的方式数，相加，是大问题的解。

返回：从开头到 s[i] 的子串中，出现『从开头到 t[j] 的子串』的次数。 即，从 前者 选字符，去匹配 后者，的方案数。

看了 s[i]==t[j] 的情况，那 s[i]!=t[j] 的情况呢？s[i] 不匹配 t[j]，唯有拿 s[i] 之前的子串去匹配

现在两种情况下的递归公式都好写了。递归树底部的 base case 呢？

随着递归压栈，子问题规模（子串长度）在变小：

小到 t 变成空串，此时 s 为了匹配它，方式只有 1 种：什么字符也不用挑（或 s 也是空串，什么都不做就匹配了，方式数也是 1）

小到 s 变成空串，但 t 不是，s 怎么也匹配不了 t，方式数为 0

递归函数的参数可以传子串或索引，但用索引描述子问题，不用每次都切割字符串，也更容易迁移到 dp 解法。

var numDistinct = function(s, t) {
	const sLen = s.length, tLen = t.length

	function helper(i, j) {
		if (j < 0) {
			return 1
		}
		if (i < 0) {
			return 0
		}

		if (s[i] == t[j]) {
            // 1. 不使用 i 去匹配 j 的方案
            // 2. 使用 i 去匹配 j 的方案
			return helper(i-1, j) + helper(i-1, j-1)
		} else {
            // i 无法匹配 j, 只能去到下一位继续匹配
			return helper(i-1, j)
		}
	}
    // 遍历顺序从后往前, 不太明白, 虽然确实只有这样才能初始化
	return helper(sLen-1, tLen-1)
};

正序无法初始化

var numDistinct = function(s, t) {
	const sLen = s.length, tLen = t.length

	function backtracking(i, j) {
        // j 为空串, 一定可以匹配
		if (j > tLen) {
			return 1
		}
        // i 为空串, 一定无法匹配
		if (i > sLen) {
			return 0
		}

		if (s[i] == t[j]) {

			return backtracking(i + 1, j) + backtracking(i + 1, j + 1)
		} else {
            
			return backtracking(i + 1, j)
		}
	}
    return backtracking(0, 0)
};

记忆化:

var numDistinct = function(s, t) {
	const sLen = s.length, tLen = t.length
	memo = new Array(sLen)
	for (let i = 0; i < sLen; i++) {
		memo[i] = new Array(tLen)
		for (let j = 0; j < tLen; j++) {
			memo[i][j] =  -1
		}
	}
	function helper(i, j) {
		if (j < 0) {
			return 1
		}
		if (i < 0) {
			return 0
		}
		if (memo[i][j] !=  -1) { 
			return memo[i][j]
		}
		if (s[i] == t[j]) {
			memo[i][j] = helper(i-1, j) + helper(i-1, j-1)
		} else {
			memo[i][j] = helper(i-1, j)
		}
		return memo[i][j]
	}
	return helper(sLen-1, tLen-1) 
};

感觉本质上还是动态规划, 有点强行递归 + 记忆化了

方案二: 动态规划

var numDistinct = function(s, t) {
	const sLen = s.length, tLen = t.length
	dp = new Array(sLen+1)
	for (let i = 0; i < sLen+1; i++) {
		dp[i] = new Array(tLen+1).fill(0)
	}
	for (let i = 0; i < sLen+1; i++) {
		for (let j = 0; j < tLen+1; j++) {
			if (j == 0) {		
				dp[i][j] = 1
			} else if (i == 0) { 
				dp[i][j] = 0
			} else {			
				if (s[i-1] == t[j-1]) {
					dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
				} else {
					dp[i][j] = dp[i-1][j]
				}
			}
		}
	}
	return dp[sLen][tLen]
}

索引优化初始化逻辑

const numDistinct = (s, t) => {
    let dp = Array.from(Array(s.length + 1), () => Array(t.length +1).fill(0));

    for(let i = 0; i <=s.length; i++) {
        dp[i][0] = 1;
    }
    
    for(let i = 1; i <= s.length; i++) {
        for(let j = 1; j<= t.length; j++) {
            if(s[i-1] === t[j-1]) {
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            } else {
                dp[i][j] = dp[i-1][j]
            }
        }
    }

    return dp[s.length][t.length];
};